//给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。 
//
// 换句话说，第一个字符串的排列之一是第二个字符串的 子串 。 
//
// 
//
// 示例 1： 
//
// 
//输入: s1 = "ab" s2 = "eidbaooo"
//输出: True
//解释: s2 包含 s1 的排列之一 ("ba").
// 
//
// 示例 2： 
//
// 
//输入: s1= "ab" s2 = "eidboaoo"
//输出: False
// 
//
// 
//
// 提示： 
//
// 
// 输入的字符串只包含小写字母 
// 两个字符串的长度都在 [1, 10,000] 之间 
// 
// Related Topics 哈希表 双指针 字符串 滑动窗口 
// 👍 370 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

public class PermutationInString {
    public static void main(String[] args) {
        Solution solution = new PermutationInString().new Solution();
        System.out.println(solution.checkInclusion("a", "ab"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 滑动窗口模板
        // s1是一个定长串，因此可以看作滑动固定长度窗口的问题
        public boolean checkInclusion(String s1, String s2) {
            int left = 0;
            int right = 0;
            int n = s2.length();
            int[] map = new int[26];
            for (char str:s1.toCharArray()){
                map[str-'a']+=1;
            }
            int total = 0;
            int k = s1.length();
            boolean flag= false;
            while (right<n){
                char curRight = s2.charAt(right);
                map[curRight-'a']-=1;
                if (map[curRight-'a']>=0) {
                    total++;
                }
                while (right-left+1>k){
                    char curLeft = s2.charAt(left);
                    map[curLeft-'a']+=1;
                    if (map[curLeft-'a']>0){
                        total--;
                    }
                    left++;
                }
                if (total==k){
                    flag=true;
                }
                right++;
            }
            return flag;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}